CS154 Spring 2003Practice Final

The practice final is below. Here are some facts about the actual final: (a) The final will be in class May 21, 12:15pm-2:30pm. (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) It has six problems and will cover the whole semester's material. Of these six problem one will be from before the first midterm, one from between midterm 1 and 2, and the remaining problem will be from after the second midterm.(d) You should bring photo ID. (e) There will be more than one version of the test. Each version will be of comparable difficulty. (f) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (g) One problem (less typos) on the actual test will be from the practice test.

1. Show that the class of recursively enumerable languages is not closed under complementation.

2. Consider the problem of whether a given Turing machine ever uses more than k tape squares. Is this problem decidable? Prove your answer.

3. Prove there is a number k such that the problem of determining whether a Turing machine M uses more than k of its states is undecidable.

4. Let B(n) be the busy beaver function. Let L be the language consisting of strings x;y such that y <= B(x). Show this language is not recursive.

5. With repect to the alphabet {0,1, start, space}, let K(x) be the smallest number n such that n viewed as a binary string is the encoding of a TM which on a blank tape outputs x. Is x recursive? Prove your answer.

6. Let L be the language consisting of strings of the form M;w such that M on input w accepts in fewer that w^|w| steps. Show this language is not in P.

7. Show that Eulerian Cycle is in P.

8. Let coNP be those languages whose complement is in NP. Show that if NP is not equal to coNP then P is not equal to NP.

9. Show 3-Colorability is NP-complete.

10. Show that there is a fixed number k such that the Bounded Tiling Language remains NP-complete even when our set of tiles is restricted to be of size k.